<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 3. Структуры Данных.Advanced</h2>
<ol>
  <li>1D запросы</li>
  <ol>
    <li>Сортированный массив и бинпоиск</li>
    <li>Дерево отрезков снизу (без групповых операций)</li>
    <li>Дерево отрезков сверху (с групповыми операциями)</li>
  </ol></li>
  <li>2D запросы</li>
  <ol>
    <li>Дерево отрезков сортированных массивов за O(log<sup>2</sup>n)</li>
    <li>Дерево отрезков set-ов, декартовых деревьев за O(log<sup>2</sup>n)</li>
    <li>fractional cascading для дерева отрезков сортированных массивов за O(logn)</li>
    <li>КД-дерево за O(sqrt(n))</li>
  </ol></li>
  <li>Фишки</li>
  <ol>
    <li>RMQ в Offline за O(1)</li>
    <li>RMQ в Online за O(log*) [рекурсивный sparse table]</li>
  </ol></li>
  <li>Persistent</li>
  <ol>
    <li>Persistent Tree за O(logn)</li>
    <li>Persistent Array за O(logn)</li>
    <li>"Persistent" задачи в Offline (обход дерева версий dfs-ом со стэком изменений)</li>
  </ol></li>
  <li>ScanLine и 2D запросы</li>
  <ol>
    <li>Точка, покрытая max количеством прямоугольников</li>
    <li>Сумма на прямоугольнике в Offline</li>
    <li>Сумма на прямоугольнике в Online (persistent)</li>
    <li>k-я порядковая статистика на отрезке в Online за O(logn)</li>
  </ol></li>
  <li>Функции на путях дерева</li>
  <ol>
    <li>Веса ребер в дереве не меняются</li>
    <ol>
      <li>Сумма = O(1)</li>
      <li>Min.Online = O(logn)</li>
      <li>Min.Offline = dfs + сжатие путей</li>
    </ol></li>
    <li>Веса ребер в дереве меняются</li>
    <ol>
      <li>2D запрос решает все</li>
      <li>Heavy-Light decomposition за O(log<sup>2</sup>n)</li>
      <li><span style="color: red; font-weight: bold;">New!</span> Upgrade Heavy-Light decomposition до O(logn)</li>
    </ol></li>
  </ol></li>
  <li>Upgrade произвольных структур данных новыми операциями</li>
  <ol>
    <li>Add &rarr; Merge (пример = количество различных чисел)</li>
    <li>Build, Get &rarr; Add, Merge (пример = самая дальняя точка по направлению)</li>
    <li>Get, Add &rarr; Del (пример = dynamic connectivity)</li>
    <li>Пополняемость/изменяемость структуры = отложенные операции.</li>
  </ol></li>
</ol>
